﻿#define _CRT_SECURE_NO_WARNINGS 1


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution
{
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals)
    {
        // 1. 按照左端点排序
        sort(intervals.begin(), intervals.end());

        // 2. 移除区间
        int ret = 0;
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++)
        {
            int a = intervals[i][0], b = intervals[i][1];
            if (a < right) // 有重叠部分
            {
                ret++; // 删掉⼀个区间
                right = min(right, b);
            }
            else // 没有重叠部分
            {
                right = b;
            }
        }
        return ret;
    }
};

int main()
{
    vector<vector<int>> intervals = { {1, 2}, {2, 3}, {3, 4}, {1, 3} };

    cout << Solution().eraseOverlapIntervals(intervals) << endl;

    return 0;
}


